﻿#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <limits>

#include "data.hpp"

namespace maze
{
	inline void GMap::advProc()
	{
		// Reset the adjacency matrix
		for (std::size_t i = 0; i < m_vertexCnt; ++i) {
			for (std::size_t j = 0; j < m_vertexCnt; ++j) {
				m_adjMatrix[i][j] = 0;
			}
		}

		// Traverse each cell in the map
		for (std::size_t row = 0; row < m_height; ++row) {
			for (std::size_t col = 0; col < m_width; ++col) {
				std::size_t currentIdx = col + row * m_width;

				// Skip if current cell is a wall
				if (m_map[row][col].attr == Attr::WALL)
					continue;

				// Check right neighbor
				if (col < m_width - 1 && m_map[row][col + 1].attr != Attr::WALL) {
					std::size_t rightIdx = (col + 1) + row * m_width;
					std::int32_t weight = m_map[row][col + 1].val;
					addEdge(currentIdx, rightIdx, weight);
				}

				// Check bottom neighbor
				if (row < m_height - 1 && m_map[row + 1][col].attr != Attr::WALL) {
					std::size_t downIdx = col + (row + 1) * m_width;
					std::int32_t weight = m_map[row + 1][col].val;
					addEdge(currentIdx, downIdx, weight);
				}
			}
		}
	}

	/**
	 * @brief 使用Dijkstra算法计算图中从起点到终点的最短路径
	 * 
	 * 该函数实现经典的Dijkstra最短路径算法，返回包含路径序列和总距离的二元组。
	 * 若不存在有效路径或输入参数无效，则返回空路径和-1。
	 * 
	 * @param start 起始顶点索引（0-based）
	 * @param end 终止顶点索引（0-based）
	 * @return std::pair<std::vector<int>, int> 
	 *         - first: 包含路径顶点索引的向量（从起点到终点）
	 *         - second: 最短路径的总距离值
	 * 
	 * @note 输入参数需满足 0 <= start/end < m_vertexCnt，否则返回空结果
	 * @see m_adjMatrix 用于存储图的邻接矩阵
	 * @see m_vertexCnt 当前图的顶点数量
	 */
	[[nodiscard]] inline auto GMap::dijkstra(int const start, int const end) const
		-> std::pair<std::vector<int>, int>
	{
		// 初始化距离数组、前驱节点数组和访问标记数组
		std::vector<int> dist(m_vertexCnt, std::numeric_limits<int>::max());
		std::vector<int> prev(m_vertexCnt, -1);
		std::vector<bool> visited(m_vertexCnt, false);

		// 参数有效性检查
		if (start < 0 || start >= m_vertexCnt || end < 0 || end >= m_vertexCnt) {
			return { std::vector<int>(), -1 };
		}

		// 设置起点距离为0
		dist[start] = 0;

		// Dijkstra算法主循环
		for (std::size_t i = 0; i < m_vertexCnt; ++i) {
			// 寻找当前未访问的最近节点
			int u = -1;
			for (std::size_t j = 0; j < m_vertexCnt; ++j) {
				if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
					u = j;
				}
			}

			// 如果未找到有效节点或距离为无穷大则终止
			if (u == -1 || dist[u] == std::numeric_limits<int>::max()) {
				break;
			}

			// 标记节点为已访问
			visited[u] = true;

			// 更新相邻节点的距离
			for (std::size_t v = 0; v < m_vertexCnt; ++v) {
				if (m_adjMatrix[u][v] != 0 && !visited[v]) {
					if (dist[v] > dist[u] + m_adjMatrix[u][v]) {
						dist[v] = dist[u] + m_adjMatrix[u][v];
						prev[v] = u;
					}
				}
			}
		}

		// 如果终点不可达返回空结果
		if (prev[end] == -1) {
			return { std::vector<int>(), -1 };
		}

		// 构建路径序列
		std::vector<int> path;
		for (int at = end; at != -1; at = prev[at]) {
			path.push_back(at);
		}
		std::reverse(path.begin(), path.end());

		// 返回最终结果
		return { path, dist[end] };
	}

	inline void GMap::printPath(const std::vector<int>& path) const
	{
		if (m_map.empty())
		{
			std::println("地图为空，无法显示路径！");
			return;
		}

		// 打印路径中各边的起止点
		if (!path.empty())
		{
			std::println("路径中的边：");
			for (size_t i = 0; i < path.size() - 1; ++i)
			{
				int src = path[i];
				int dest = path[i + 1];

				// 检查顶点索引是否合法
				if (src < 0 || src >= static_cast<int>(m_vertexCnt) ||
					dest < 0 || dest >= static_cast<int>(m_vertexCnt))
				{
					std::println("路径包含非法顶点索引：{} -> {}", src, dest);
					continue;
				}

				int row1 = src / static_cast<int>(m_width);
				int col1 = src % static_cast<int>(m_width);
				int row2 = dest / static_cast<int>(m_width);
				int col2 = dest % static_cast<int>(m_width);

				std::println("({:2}, {:2}) -> ({:2}, {:2})", row1, col1, row2, col2);
			}
			std::println();
		}

		constexpr int wide{ 3 };
		// 打印列号
		{
			auto col = Color(CName::CYAN);
			std::print(R"(L\C )");
			for (auto i = 0u; i < m_width; ++i)
			{
				std::print("{: <{}} ", i + 1, wide);
			}
			std::print("\n");
		}

		// 打印矩阵和行号
		for (std::size_t i = 0; i < m_height; ++i)
		{
			// 打印行号
			{
				auto row_col = Color(CName::GREEN);
				std::print("{: <{}} ", i + 1, wide);
			}

			for (std::size_t j = 0; j < m_width; ++j)
			{
				auto ele_col = Color(CName::WHITE);
				auto vertex = i * m_width + j;
				bool isInPath = std::find(path.begin(), path.end(), vertex) != path.end();

				switch (m_map[i][j].attr)
				{
					case Attr::ROAD:
						if (isInPath)
						{
							ele_col.setPrn(CName::WHITE);
							std::print("{: <{}} ", "◇", wide); // 路径上的路
						}
						else
						{
							std::print("{: <{}} ", "路", wide);
						}
						break;
					case Attr::WALL:
						ele_col.setPrn(CName::YELLOW);
						std::print("{: <{}} ", "墙", wide);
						break;
					case Attr::TRAP:
						if (isInPath)
						{
							ele_col.setPrn(CName::YELLOW);
							std::print("{: <{}} ", "◇", wide); // 路径上的陷阱
						}
						else
						{
							ele_col.setPrn(CName::RED);
							std::print("{: <{}} ", "陷", wide);
						}
						break;
					case Attr::TREASURE:
						if (isInPath)
						{
							ele_col.setPrn(CName::BLUE);
							std::print("{: <{}} ", "◇", wide); // 路径上的宝藏
						}
						else
						{
							ele_col.setPrn(CName::BLUE);
							std::print("{: <{}} ", "宝", wide);
						}
						break;
					default:
						std::print("{: <{}} ", "？", wide);
				}
			}
			std::print("\n");
		}
		std::println();
	}

	inline void GMap::printPath2(const std::vector<int>&path) const
	{

		// 检查地图是否为空
		if (m_map.empty())
		{
			std::println("地图为空，无法显示路径！");
			return;
		}

		// 检查路径是否为空
		if (path.empty())
		{
			std::println("路径为空，无法绘制！");
			return;
		}

		// 创建一个二维布尔数组表示是否在路径上
		std::vector<std::vector<bool>> onPath(m_height, std::vector<bool>(m_width, false));

		// 遍历路径，标记路径点及其连线
		for (size_t i = 0; i < path.size(); ++i)
		{
			int vertex = path[i];

			// 检查顶点索引是否合法
			if (vertex < 0 || vertex >= static_cast<int>(m_vertexCnt))
			{
				std::println("路径包含非法顶点索引：{}", vertex);
				return;
			}

			int row = vertex / static_cast<int>(m_width);
			int col = vertex % static_cast<int>(m_width);

			// 标记路径点
			onPath[row][col] = true;

			// 如果不是最后一个点，绘制与下一个点之间的连线
			if (i + 1 < path.size())
			{
				int next_vertex = path[i + 1];
				if (next_vertex < 0 || next_vertex >= static_cast<int>(m_vertexCnt))
				{
					std::println("路径包含非法顶点索引：{}", next_vertex);
					return;
				}

				int next_row = next_vertex / static_cast<int>(m_width);
				int next_col = next_vertex % static_cast<int>(m_width);

				// 水平方向移动
				if (row == next_row)
				{
					int start_col = std::min(col, next_col);
					int end_col = std::max(col, next_col);

					for (int c = start_col + 1; c < end_col; ++c)
					{
						if (m_map[row][c].attr == Attr::WALL)
						{
							std::println("路径非法：路径穿过墙，无法绘制！");
							return;
						}
						onPath[row][c] = true;
					}
				}
				// 垂直方向移动
				else if (col == next_col)
				{
					int start_row = std::min(row, next_row);
					int end_row = std::max(row, next_row);

					for (int r = start_row + 1; r < end_row; ++r)
					{
						if (m_map[r][col].attr == Attr::WALL)
						{
							std::println("路径非法：路径穿过墙，无法绘制！");
							return;
						}
						onPath[r][col] = true;
					}
				}
				else
				{
					std::println("路径非法：非水平或垂直移动！");
					return;
				}
			}
		}

		// 打印地图并显示路径
		constexpr int wide{ 4 }; // 宽度用于格式化输出

		// 打印列号
		{
			auto col = Color(CName::CYAN);
			std::print(R"(L\C  )");
			for (auto i = 0u; i < m_width; ++i)
			{
				std::print("{: <{}} ", i + 1, wide);
			}
			std::print("\n");
		}

		// 打印矩阵和行号
		for (std::size_t i = 0; i < m_height; ++i)
		{
			// 打印行号
			{
				auto row_col = Color(CName::GREEN);
				std::print("{: <{}} ", i + 1, wide);
			}

			for (std::size_t j = 0; j < m_width; ++j)
			{
				auto ele_col = Color(CName::WHITE);
				bool isInPath = onPath[i][j];

				switch (m_map[i][j].attr)
				{
					case Attr::ROAD:
						if (isInPath)
						{
							ele_col.setPrn(CName::WHITE);
							std::print("{: <{}} ", "◇ ", wide); // 路径上的路
						}
						else
						{
							std::print("{: <{}} ", "路", wide);
						}
						break;
					case Attr::WALL:
						ele_col.setPrn(CName::YELLOW);
						std::print("{: <{}} ", "墙", wide);
						break;
					case Attr::TRAP:
						if (isInPath)
						{
							ele_col.setPrn(CName::YELLOW);
							std::print("{: <{}} ", "◇", wide); // 路径上的陷阱
						}
						else
						{
							ele_col.setPrn(CName::RED);
							std::print("{: <{}} ", "陷", wide);
						}
						break;
					case Attr::TREASURE:
						if (isInPath)
						{
							ele_col.setPrn(CName::BLUE);
							std::print("{: <{}} ", "◇", wide); // 路径上的宝藏
						}
						else
						{
							ele_col.setPrn(CName::BLUE);
							std::print("{: <{}} ", "宝", wide);
						}
						break;
					default:
						std::print("{: <{}} ", "？", wide);
				}
			}
			std::print("\n");
		}

		std::println();
	}
}